package com.algorithm;

import com.immomo.mcf.util.StringUtils;
import jdk.internal.util.xml.impl.Pair;

import java.util.*;

/**
 * @author: sun.hongliang
 * @create: 2019/12/11 15:28
 */
public class BInTreeTest {
    public static void main(String[] args) {
//        TreeNode[] node = new TreeNode[10];//以数组形式生成一棵完全二叉树
//        for (int i = 0; i < 10; i++) {
//            node[i] = new TreeNode(i + 1);
//        }
//        for (int i = 0; i < 10; i++) {
//            if (i * 2 + 1 < 10)
//                node[i].left = node[i * 2 + 1];
//            if (i * 2 + 2 < 10)
//                node[i].right = node[i * 2 + 2];
//        }
//        dfs(node[0]);
//        System.out.println("=====");
//        preOrder(node[0]);
        String city = "北京市";
        String c = StringUtils.replace(city, "市", "");
        System.out.println(c);
    }

    public boolean isValidBST(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        midOrder(root, list);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) < list.get(i - 1)) {
                return false;
            }
        }
        return true;
    }

    public void midOrder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        midOrder(root.left, list);
        list.add(root.val);
        midOrder(root.right, list);
    }

    public static void dfs(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        Stack<List<Integer>> pathSack = new Stack<>();
        if (root == null)
            return;
        stack.push(root);
        pathSack.push(Arrays.asList(root.val));
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            List<Integer> path = pathSack.pop();
            if (node.left == null && node.right == null) {
                System.out.println(path);
            }
            if (node.right != null) {
                stack.push(node.right);
                ArrayList<Integer> integers = new ArrayList<>(path);
                integers.add(node.right.val);
                pathSack.push(integers);
            }
            if (node.left != null) {
                stack.push(node.left);
                ArrayList<Integer> integers = new ArrayList<>(path);
                integers.add(node.left.val);
                pathSack.push(integers);
            }
        }
    }

    public static void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    public static void midOrder(TreeNode root) {
        if (root == null) return;
        midOrder(root.left);
        System.out.println(root.val);
        midOrder(root.right);
    }

    public static void preOrderStack(TreeNode r) {
        TreeNode root = r;
        Stack<TreeNode> nodeStack = new Stack<>();
        while (root != null || !nodeStack.isEmpty()) {
            while (root != null) {
                System.out.println(root.val);
                nodeStack.push(root);
                root = root.left;
            }
            if (!nodeStack.isEmpty()) {
                root = nodeStack.pop();
                root = root.right;
            }
        }
    }

    public static void levOrder(TreeNode r) {
        TreeNode root = r;
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        while (!list.isEmpty()) {
            TreeNode poll = list.poll();
            System.out.println(poll.val);
            if (poll.left != null) {
                list.offer(poll.left);
            }
            if (poll.right != null) {
                list.offer(poll.right);
            }
        }
    }


    public static void midOrderStack(TreeNode r) {
        TreeNode root = r;
        Stack<TreeNode> nodeStack = new Stack<>();
        while (root != null || !nodeStack.isEmpty()) {
            while (root != null) {
                nodeStack.push(root);
                root = root.left;
            }
            if (!nodeStack.isEmpty()) {
                root = nodeStack.pop();
                System.out.println(root.val);
                root = root.right;
            }
        }
    }

    private static List<Integer> sortTList(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode p = root;
        Stack<TreeNode> stack = new Stack<>();
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            if (!stack.isEmpty()) {
                p = stack.pop();
                res.add(p.val);
                p = p.right;
            }
        }
        return res;
    }


    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode t = root;
        Stack<TreeNode> stack = new Stack<>();
        boolean flg = false;
        while (t != null || !stack.isEmpty()) {
            while (t != null) {
                stack.push(t);
                t = t.left;
            }
            if (!stack.isEmpty()) {
                t = stack.pop();
                if (flg) {
                    return t;
                }
                if (t == p) {
                    flg = true;
                }
                t = t.right;
            }
        }
        return null;
    }


}
